package com.ljx.offer;

import org.junit.Test;

import java.util.HashMap;
import java.util.HashSet;

/**
 * @author 李捷禧
 * Date: 2023/3/25
 * ClassName: C_13
 */

public class C_13 {
    //优化1：
    //更容易理解
    int an,bm;
    boolean[][] visited;
    public int movingCount2(int m, int n, int k) {
        this.an = n;
        this.bm = m;
        this.visited = new boolean[bm][an];
        return pdd(0,0,k);
    }

    private int pdd(int i, int j, int k) {
        if(i >= bm || j >= an || visited[i][j] || k < num(i,j)) return 0;
        visited[i][j] = true;
        return 1 + pdd(i+1,j,k) + pdd(i,j+1,k);
    }

    //因为n ，m都小于100
    int num(int i, int j){
        return (i % 10) + (i / 10) + (j % 10) + (j / 10);
    }

    //优化二：
    int n,m,k;
    boolean[][] res;
    public int movingCount(int m, int n, int k) {
        this.m = m;
        this.n = n;
        this.k = k;
        this.res = new boolean[m][n];
        return dfs(0,0,0,0);
    }

    public int dfs(int i, int j, int sn, int sm) {
        if( i >= m || j >= n || k < sn+sm || res[i][j]) return 0;
        res[i][j] = true;
        return 1 + dfs(i + 1,j,(i+1) % 10 != 0 ? sn+1 : sn-8,sm) + dfs(i,j+1,sn,(j+1) % 10 != 0 ? sm + 1 : sm -8);
    }

    /**
     * 为什么到10过后就没算了？
     * 10%10 + 1  == 2 < k
     * 为啥就不行呢
     * 9都到不了，还怎么到10？
     * @param m
     * @param n
     * @param k
     * @return
     */
    public int movingCount1(int m, int n, int k) {
        int count = 0;
        if(m > k && k != 9) m = k + 1;
        if(n > k && k != 9) n = k + 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int num = (i % 10) + (i / 10) + (j % 10) + (j / 10);
                if(k >= num ) {
                    count ++;
                }
            }
        }
        return count;
    }

    @Test
    public void test(){
        System.out.println(movingCount(16,8,4));
    }


}
